package com.zk.algorithm;

import com.zk.algorithm.annotation.Hard;
import com.zk.algorithm.annotation.LeetCodeExplore;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * 这个需要返回所有的顺序
 * return the ordering of courses you should take to finish all courses.
 */
@LeetCodeExplore
@Hard
public class CourseSchedule2 {

    public static void main(String...args) {
        Utils.println(new CourseSchedule2().findOrder(3, new int[][]{
                {1,0},
                {1,2},
                {0,1}
        }));
    }

    public int[] findOrder(int numCourses, int[][] prerequisites) {
        Queue<Integer> queue = new LinkedList<Integer>();
        int[] indegrees = new int[numCourses];

        List<Integer> result = new ArrayList<Integer>(numCourses);

        // 所有入度
        for (int i=0; i<prerequisites.length; i++) {
            indegrees[ prerequisites[i][0] ]++;
        }

        // 所有入度为 0 的进去队列
        for (int i=0; i<indegrees.length; i++) {
            if (indegrees[i] == 0) {
                queue.offer(i);
            }
        }

        while (!queue.isEmpty()) {

            int course = queue.poll();
            result.add(course);

            for (int i=0; i<prerequisites.length; i++) {
                if (prerequisites[i][1] == course) {

                    // 入度--
                    indegrees[prerequisites[i][0]]--;

                    if (indegrees[prerequisites[i][0]] == 0) { // 始终入出度为 0 的
                        queue.offer(prerequisites[i][0]);
                    }

                }
            }

        }

        if (result.size() == numCourses) {
            return result.stream().mapToInt(Integer::intValue).toArray();
        }

        return new int[]{};
    }

}
